package hot;

public class Num79 {
    boolean ex = false;
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        boolean[][] b = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                dfs(board,b,word,0,i,j);
            }
        }
        return ex;
    }
    public void dfs(char[][] board,boolean[][] b,String word,int index,int i,int j) {
        if(word.charAt(index) != board[i][j]) {
            return;
        }
        if(index == word.length() - 1) {
            ex = true;
            return;
        }
        b[i][j] = true;
        int[][] arr = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        for(int[] nums : arr) {
            i += nums[0];
            j += nums[1];
            index += 1;
            if(i >= 0 && i < board.length && j >= 0 && j < board[0].length && b[i][j] == false) {
                dfs(board,b,word,index,i,j);
            }
            i -= nums[0];
            j -= nums[1];
            index -= 1;
        }
        b[i][j] = false;
    }
}
